#include<bits/stdc++.h>
using namespace std;
int T,n,q;
int s,t;
int gcd(int s,int t){
	if(s<t) swap(s,t);
	int c=s%t;
	while(c){
		s=t;
		t=c;
		c=s%t;
	}
	return t;
}
int main(){
	scanf("%d",&T);
	for(int i=0;i<T;i++){
		scanf("%d%d",&n,&q);
		for(int j=0;j<q;j++){
			scanf("%d%d",&s,&t);
			int m=gcd(s,t);
			printf("%d\n",abs(m-s)+abs(m-t));
		}
	}
	return 0;
}
